/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._1306;

/**
 * 这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。
 * <p>
 * 请你判断自己是否能够跳到对应元素值为 0 的 任意 下标处。
 * <p>
 * 注意，不管是什么情况下，你都无法跳到数组之外。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：arr = [4,2,3,0,3,1,2], start = 5
 * 输出：true
 * 解释：
 * 到达值为 0 的下标 3 有以下可能方案：
 * 下标 5 -> 下标 4 -> 下标 1 -> 下标 3
 * 下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3
 * 示例 2：
 * <p>
 * 输入：arr = [4,2,3,0,3,1,2], start = 0
 * 输出：true
 * 解释：
 * 到达值为 0 的下标 3 有以下可能方案：
 * 下标 0 -> 下标 4 -> 下标 1 -> 下标 3
 * 示例 3：
 * <p>
 * 输入：arr = [3,0,2,1,2], start = 2
 * 输出：false
 * 解释：无法到达值为 0 的下标 1 处。
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= arr.length <= 5 * 10^4
 * 0 <= arr[i] < arr.length
 * 0 <= start < arr.length
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._1306
 * @ClassName: JumpGameIII
 * @Author: linyaonan
 * @Date: 2020/1/22 10:30
 */
public class JumpGameIII {

    private int[] arr;
    private int len;
    private boolean[] visited;

    public boolean canReach(int[] arr, int start) {
        // 原始数组
        this.arr = arr;
        // 数组最大范围
        len = arr.length;
        // 节点是否已经走过
        visited = new boolean[len];
        return backTrack(start);
    }

    private boolean backTrack(int from) {
        // 递归中断，回溯
        if (from < 0 || from >= len || visited[from]) {
            return false;
        }

        if (arr[from] == 0) {
            return true;
        }

        visited[from] = true;
        // 递归，双方向
        return backTrack(from + arr[from]) || backTrack(from - arr[from]);
    }
}
